#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    string robotWithString(string s) {
        int n = s.size();
        stack<char> stk;
        vector<char> suf_min(n + 1, 'z');
        suf_min[n - 1] = s[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            suf_min[i] = min(suf_min[i + 1], s[i]);
        }
        string res;
        for (int i = 0; i < n; i++)
        {
            stk.push(s[i]);
            while (stk.size() && stk.top() <= suf_min[i + 1])
            {
                res += stk.top(); stk.pop();
            }
        }
        return res;
    }
};